/*************************************************************************
	> File Name: 084.柱状图中最大的矩形.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 一  9/ 6 17:16:45 2021
 ************************************************************************/

int largestRectangleArea(int* heights, int heightsSize){
    int n = heightsSize;
    int left[n], right[n];
    int ans = 0;
    int mono_stack[n], top = -1;
    //分别找到并记录每根柱子左侧和右侧第一个小于该柱子高度的位置
    for (int i = 0; i < n; i++) {
        right[i] = n;
        while (top != -1 && heights[mono_stack[top]] >= heights[i]) {
            right[mono_stack[top]] = i; //栈顶位置的右侧第一个小于该高度的就是i位置的柱子
            top--;
        }
        left[i] = top == -1 ? -1 : mono_stack[top];
        mono_stack[++top] = i;
    }

    for (int i = 0; i < n; i++) {
        ans = fmax(ans, (right[i] - left[i] - 1) * heights[i]);
    }
    return ans;
}
